package com.zhengwl.study.datastruct;

import net.sf.cglib.transform.impl.AddDelegateTransformer;

public class DuLinkList<T> {
	private class Node {
		private T data;
		private Node prev;
		private Node next;

		public Node() {
		}

		public Node(T data, Node prev, Node next) {
			this.data = data;
			this.prev = prev;
			this.next = next;
		}
	}

	private Node header;
	private Node tail;

	private int size;

	public DuLinkList() {
		header = null;
		tail = null;
	}

	public DuLinkList(T ele) {
		header = new Node(ele, null, null);
		tail = header;
		size++;
	}

	public int length() {
		return size;
	}

	public T get(int index) {
		return getNodeByIndex(index).data;
	}

	private Node getNodeByIndex(int index) {
		if (index < 0 || index > size - 1) {
			throw new IndexOutOfBoundsException("链表索引越界");
		}
		if (index <= size / 2) {
			Node current = header;
			for (int i = 0; i < size / 2 && current != null; i++, current = current.next) {
				if (i == index) {
					return current;
				}
			}
		} else {
			Node current = tail;
			for (int i = 0; i > size / 2 && current != null; i++, current = current.prev) {
				if (i == index) {
					return current;
				}
			}
		}
		return null;
	}

	public int indexOf(T ele) {
		Node current = header;
		for (int i = 0; i < size && current != null; i++, current = current.next) {
			if (current.data.equals(ele)) {
				return i;
			}
		}
		return -1;
	}

	public void insert(T ele, int index) {
		if (index < 0 || index > size) {
			throw new IndexOutOfBoundsException("链表越界");
		}

		if (header == null) {
			add(ele);
		}else {
			if(index==0){
				addAtHeader(ele);
			}else {
				Node prev=getNodeByIndex(index-1);
				Node next=prev.next;
				Node newNode=new  Node(ele,prev,next);
				prev.next=newNode;
				next.prev=newNode;
				size++;
			}
		}
	}

	// 采用尾插法为链表添加新节点
	public void add(T ele) {
		if(header==null){
			header=new Node(ele,null,null);
			tail=header;
		}else {
			Node newNode=new Node(ele,tail,null);
			tail.next=newNode;
			tail=newNode ;
		}
		size++;
	}
	
	public void addAtHeader(T ele) {
		header=new Node(ele,null,header);
		if(tail==null){
			tail=header;
		}
		size++;		
	}
	
	public T  delete(int index) {
		if(index<0||index>size-1){
			throw new IndexOutOfBoundsException("链表越界");
			
		}
		Node del=null;
		if(index==0){
			del=header;
			header=header.next;
			header.prev=null;
		}else {
			Node prev=getNodeByIndex(index-1);
			del=prev.next;
			if(del.next!=null){
				del.next.prev=prev;
			}
			del.prev=null;
			del.next=null;			
		}
		size--;
		return del.data;
	}

}
